package chapter05_string;

import com.sun.javafx.sg.prism.web.NGWebView;

/**
 * 描述：
 *      给定一个整数n，求只由0和1组成长度为N的所有字符串中，满足0字符的左边必有一个1字符的字符串数量
 * @author hl
 * @date 2021/9/16 21:10
 */
public class OneLeftZero {
    public static void main(String[] args) {
        OneLeftZero main = new OneLeftZero();
        int count1 = main.getNum1(5);
        int count2 = main.getNum1(5);
        System.out.println(count1);
        System.out.println(count2);

    }


    /**
     * 递推
     *      最高位只能为1
     *      定义p(i)表示i-1下标的字符已经确定的情况下，i~n-1位置所有满足条件的字符串的数量
     *      在i-1位置已经确定为1的情况下，那么i位置可以是0，也可以是1，i~n-1上满足条件的数量为p(i+1)
     *      在i-1位置已经确定为0的情况下，那么i位置只能是1，i~n-1上满足条件的数量为p(i+2)
     *      因此p(i) = p(i + 1) + p(i + 2)
     *      特殊位置p(N)=1, p(N-1)表示n-1位置上可以为0也可以为1
     * @param n
     * @return
     */
    public int getNum1(int n){
        if (n < 1) {
            return 0;
        }
        return process(n, 1);
    }

    private int process(int n, int i) {
        if (i == n - 1) {
            return 2;
        }
        if (i == n) {
            return 1;
        }
        return process(n, i + 1) + process(n, i + 2);
    }

    /**
     * 由以上可得知其实就是求解的过程也就是求斐波那契数列的过程，因此可以使用递归达到时间复杂度O(N)
     * 只不过该数列的起始项是1,2
     * @param n
     * @return
     */
    public int getNum2(int n){
        if (n < 1) {
            return 0;
        }
        if (n == 1) {
            return n;
        }
        int pre = 1, cur = 1, tmp = 0;
        for (int i = 2; i <= n; i++) {
            tmp = cur;
            cur = cur + pre;
            pre = tmp;
        }
        return cur;
    }
    public int getNum3(int n){
        if (n < 1) {
            return 0;
        }
        if (n < 3) {
            return n;
        }
        int s1 = 1, s2 = 2, tmp = 0;
        for (int i = 2; i < n - 1; i++) {
            tmp = s2;
            s2 = s1 + s2;
            s1 = tmp;
        }
        return s2;
    }
}
